1. Field of the Invention
The present inventions relates to bus arbitration and in particular to a bus arbitration method and structure for improving fairness in priority-based allocation of a shared bus among multiple requesting master devices.
2. Discussion of Related Art
It is generally known in electronic systems to have multiple devices communicating over a shared electronic bus. In general, a first device (usually referred to as a master device) initiates an exchange of information with a second device (usually referred to as a slave device). It is also generally known in the art that a bus structure may permit multiple master devices and multiple slave devices to exchange information. Generally, one master device communicates with one or more slave devices to the exclusion of other master and slave devices in the system. In such a circumstance, a first master device desiring use of the bus for communication with a slave device must first obtain temporary exclusive control over the shared bus structure. A master device obtains temporary exclusive control of the shared bus by requesting the bus structure and awaiting an acknowledgment signal indicative of granting of the requested temporary exclusive access to the shared bus.
Typically, an arbiter device coupled to the shared bus structure receives a request for temporary exclusive control of the bus from each of several master devices and selects the next master device to obtain the requested temporary exclusive control. The arbiter receives request signals and returns grant (acknowledgment) signals to master devices to indicate request and granting of temporary exclusive control, respectively. This process is typically referred to as the bus arbitration. A number of well-known commercially applied bus structures support such multiple master devices sharing control of a bus. Though the specific timing and signals involved in arbitration may vary, all such buses support arbitration in some form.
It is common in the art for an arbiter device to utilize any of several well-known techniques for determining the next requesting master device to be granted temporary exclusive control of the shared bus structure. One simple technique is often referred to as “round-robin” in that each device may be granted temporary exclusive control of the shared bus in sequential order defined by an index number—usually a master device ID. When the last master device ID is granted temporary exclusive control over the bus, the first master device is again eligible for exclusive bus control. This sequential “round-robin” technique assures that each master device has a roughly equal opportunity to obtain temporary exclusive control of the shared bus structure.
Another common bus arbitration technique is to assign a priority to each master device. At any given point, a master device with the highest priority requesting temporary exclusive control of the shared bus will be granted control over the bus. Still other techniques combine features of both a priority-based scheme and round-robin arbitration techniques. For example, each master device may be assigned a priority and all master devices having the same particular priority level share the bus using a round-robin technique.
Strict round-robins arbitration generally provides equal access to the shared bus for all master devices. Standard priority-based bus arbitration algorithms are effective at assuring that the highest priority master devices can rapidly access the shared bus as compared to lower priority devices. However a problem with priority-based scheme is that the lowest priority devices may be effectively “starved” from access to the bus due to high frequency bus requests by higher priority master devices. By contrast, round-robin arbitration techniques preclude high priority master devices from obtaining necessary frequent access to a shared bus.
Hybrid techniques, as noted above, that combine features of both round-robin arbitration and priority-based arbitration still produce unfair results in some circumstances. For example, presume a plurality of master devices are requesting the bus all at the same first priority level (i.e., applying round-robin techniques within that priority level). A higher priority master device then requests and is granted the bus (since it is a higher priority than the plurality of devices at the first priority level). When the higher priority device relinquishes the bus, the plurality of devices at the first priority level again arbitrate using round-robin techniques. However, present techniques restart the round-robin selection process in the arbitration. Thus round-robin arbitration within a priority level is not assured to fairly allocate the bus to all devices within that priority level when arbitration is interrupted by a higher priority master device request.
It is evident from the above discussion that a need exists for improved arbitration techniques that provide additional fairness to lower priority master devices while granting frequent access to high priority master devices.